package code;

import java.util.Arrays;

public class CountConsitentKeys {

	public static int MAXN = 2000001;

    public static int[][] tree = new int[MAXN][12];

    public static int[] pass = new int[MAXN];

    //每次字符串遍历结束，对应尾部位置++
    public static int[] end = new int[MAXN];

    //cnt用于为每个创建的节点进行编号
    public static int cnt;

    public static void build() {
        cnt = 1;
    }

    //如果一个数的差值>=10，那么将10变为1->0，而不是直接将10存入，这是因为差值可能非常大
    //在此基础上，可能出现的值为： 0-9，#，-
    // -表示负号
    //每个差值后都要添加一个#，这是为了辨别差值是哪个，因为要将所有差值构造字符串，如果字符串为"123"，
    //那么是差值1=1和差值2=23，还是差值1=12和差值2=3，还是差值=123，还是。。。。
    //故用#进行分割每个差值
    public static int path(char cha) {
        if (cha == '#') {
            return 10;
        } else if (cha == '-') {
            return 11;
        } else {
            return cha - '0';
        }
    }


    //插入字符串word
    public static void insert(String word) {
        int cur = 1;
        pass[cur]++;
        for (int i = 0; i < word.length(); i++) {
            int path = path(word.charAt(i));
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
        end[cur]++;
    }

    //返回字符串word出现的次数
    public static int search(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = path(word.charAt(i));
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return end[cur];
    }

    //返回以pre作为前缀的字符串个数
    public static int prefixNumber(String pre) {
        int cur = 1;
        for (int i = 0; i < pre.length(); i++) {
            int path = path(pre.charAt(i));
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return pass[cur];
    }


    //清空数据
    public static void clear() {
        for (int i = 0; i <= cnt; i++) {
            Arrays.fill(tree[i], 0);
            pass[i] = 0;
            end[i] = 0;
        }
    }
    public int[] countConsistentKeys (int[][] b, int[][] a) {
        // write code here
        build();
        int[] ans = new int[b.length];
        //将a中的每个数组构建字符串
        for (int i = 0; i < a.length; i++) {
            StringBuilder str = new StringBuilder();
            for (int j = 0; j < a[i].length - 1; j++) {
                str.append(String.valueOf(a[i][j + 1] - a[i][j]) + "#");
            }
            insert(str.toString());
        }
        //将b中的每个数组构造字符串
        for (int i = 0; i < b.length; i++) {
            StringBuilder str = new StringBuilder();
            for (int j = 0; j < b[i].length - 1; j++) {
                str.append(String.valueOf(b[i][j + 1] - b[i][j]) + "#");
            }
            //对每个字符串在前缀树中查询
            ans[i] = prefixNumber(str.toString());
        }
        clear();
        return ans;
    }
}
